home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / applic / ntp / kent.shar / ksb.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-29  |  7.3 KB  |  269 lines
  1. /* ----------------------------------------------------------------- */
  2. /* This DES software was developed by Steve Kent and John Linn       */
  3. /* of BBN Communications Corporation, Cambridge, MA                  */
  4. /* Do not redistribute this software, or integrate with other        */
  5. /* software, without preserving this notice                          */
  6. /* ----------------------------------------------------------------- */
  7.  
  8. /* ksb.c -- John Linn, 21 April 1983 --
  9.    This program uses an optimized, table-driven method to compute a
  10.    DES key schedule from 8 input bytes.
  11.    Once the optimizing table (pc2otab) has been computed, generation
  12.    of a schedule takes approximately 12 user ms on a C/70.
  13.  
  14.    Note: there is still room to optimize pc1 and tweak out a couple
  15.    of extra milliseconds from the key schedule build, but this
  16.    should only be important if and when adaptation to an environment
  17.    which needs to dynamically change keys is considered.
  18.  
  19.    21 Apr. -- removed c30 special case. c30 now takes same key format,
  20.    and output is always to file 'ks'.
  21.  
  22.    6 May -- added command line option to specify name of output file.
  23.    if no command arg, output is still to 'ks'.
  24.  
  25. */
  26.  
  27. #include <stdio.h>
  28.  
  29. /* tables to describe permutations, per NBS FIPS */
  30.  
  31. static int pc1c [] =
  32.     { 57, 49, 41, 33, 25, 17, 9,
  33.       1, 58, 50, 42, 34, 26, 18,
  34.       10, 2, 59, 51, 43, 35, 27,
  35.       19, 11, 3, 60, 52, 44, 36 };
  36.  
  37. static int pc1d [] =
  38.     { 63, 55, 47, 39, 31, 23, 15,
  39.       7, 62, 54, 46, 38, 30, 22,
  40.       14, 6, 61, 53, 45, 37, 29,
  41.       21, 13, 5, 28, 20, 12, 4 };
  42.  
  43. static int shiftsked []=
  44.     { 1, 1, 2, 2, 2, 2, 2, 2,
  45.       1, 2, 2, 2, 2, 2, 2, 1 };
  46.  
  47. static int pc2 [] =
  48.     { 14, 17, 11, 24, 1, 5,
  49.       3, 28, 15, 6, 21, 10,
  50.       23, 19, 12, 4, 26, 8,
  51.       16, 7, 27, 20, 13, 2,
  52.       41, 52, 31, 37, 47, 55,
  53.       30, 40, 51, 45, 33, 48,
  54.       44, 49, 39, 56, 34, 53,
  55.       46, 42, 50, 36, 29, 32 };
  56.  
  57. /* --- some bit manipulation primitives --- */
  58.  
  59. /* g_keybit -- extract bit bnum from the key in inkey */
  60. #define g_keybit(bnum) (01 & (inkey [bnum/8] >> (8 - (bnum%8))))
  61.  
  62. long    lrot28 (lval)
  63. /* do left rotate of 28 bit quantity */
  64. long    lval;
  65. {
  66.   lval <<= 1;
  67.   if (0X10000000L & lval) lval++;
  68.   lval &= 0XFFFFFFFL;
  69.   return (lval);
  70. }
  71.  
  72. /* --- following code and data does key schedule generation --- */
  73.  
  74. unsigned skedkeys [16] [4];
  75.  
  76. unsigned inkey [8];     /* input key goes here */
  77.  
  78. long pc2otab [8] [128]; /* table to optimize pc2 */
  79.  
  80. spc2otab ()     /* initialize pc2otab for pc2 lookups */
  81. {
  82. #define NOTSEL  -1
  83.  
  84.   extern long pc2otab [8] [128];
  85.   extern int pc2 [48];
  86.   
  87.   int bn, bv, bitloc, i;
  88.   int bitindx [7];
  89.  
  90.   for (bn = 0; bn < 8; bn++)    /* each input 7-bit byte, l->r */
  91.   {
  92.     for (i = 0; i < 7; i++)     /* find each bit in the byte */
  93.     {
  94.     /* determine where (or if) pc2 places the given bit in the
  95.        output.  set bitindx [0] to the bit number (1->48,l->r)
  96.        where the MSB of the byte occurs, or to NOTSEL if pc2
  97.        doesn't pick it. similar down through bitindx [6]. */
  98.  
  99.       for (bitloc = 0; bitloc < 48; bitloc++)
  100.       {
  101.     /* trying until a match in pc2 found or table exhausted */
  102.         if (pc2 [bitloc] == (1 + ((bn * 7) + i)))
  103.         {
  104.           bitindx [i] = bitloc + 1;
  105.           break;
  106.         } 
  107.       }
  108.       if (bitloc == 48) bitindx [i] = NOTSEL;
  109.     }
  110.  
  111.     for (bv = 0; bv < 128; bv++)
  112.     {
  113.       /* setting up a table entry for each input byte value */
  114.       pc2otab [bn] [bv] = 0L;
  115.       if (bn < 4)       /* this is left word (nbs bits 1-24) */
  116.       {
  117.     for (i = 0; i < 7; i++)
  118.     {
  119.        if (NOTSEL == bitindx [i]) continue;
  120.         if (bv & (01 << (6 - i)))
  121.           pc2otab [bn] [bv] |= (0X1L << (24 - bitindx [i]));
  122.     }
  123.       }
  124.       else              /* this is right word (nbs bits 25-48) */
  125.       {
  126.     for (i = 0; i < 7; i++)
  127.     {
  128.           if (NOTSEL == bitindx [i]) continue;
  129.            if (bv & (01 << (6 - i)))
  130.              pc2otab [bn] [bv] |= (0X1L << (48 - bitindx [i]));
  131.     }
  132.       }
  133.     }
  134.   }
  135. }
  136.  
  137. ksmake ()       /* Make a key schedule from key bytes in inkey */
  138. {
  139.   extern unsigned skedkeys [16] [4];
  140.   extern long pc2otab [8] [128];
  141.  
  142.   int   round;
  143.   long  pcct, pcdt;
  144.   long  pc2out [2];
  145.   int   i;
  146.  
  147.   /* do pc-1 permutation, extracting bits from inkey */
  148.   pcct = pcdt = 0L;
  149.   for (i = 0; i < 27; i++)   
  150.    /* filling all appropriate bits */
  151.   {
  152.     pcct |= g_keybit(pc1c [i]);
  153.     pcdt |= g_keybit(pc1d [i]);
  154.     pcct <<= 1;
  155.     pcdt <<= 1;
  156.   }
  157.   /* one final ior, without a shift */
  158.   pcct |= g_keybit(pc1c [i]);
  159.   pcdt |= g_keybit(pc1d [i]);
  160.  
  161.   for (round = 0; round < 16; round++)
  162.   {
  163.     /* always at least one shift */
  164.     pcct = lrot28 (pcct);
  165.     pcdt = lrot28 (pcdt);
  166.  
  167.     if (shiftsked [round] == 2)
  168.     {   /* this round needs another shift */
  169.       pcct = lrot28 (pcct);
  170.       pcdt = lrot28 (pcdt);
  171.     } 
  172.  
  173.     /* Now, pcct and pcdt have the values on which we can apply
  174.        pc2 and select the key bits, storing them in pc2out[0] and
  175.        pc2out[1]. The high order [pc2out[0]] bits all come from
  176.        pcct, and the low order from pcdt. */
  177.  
  178.     pc2out [0] = pc2otab [0] [pcct >> 21];
  179.     pc2out [0] |= pc2otab [1] [0X7F & (pcct >> 14)];
  180.     pc2out [0] |= pc2otab [2] [0X7F & (pcct >> 7)];
  181.     pc2out [0] |= pc2otab [3] [0X7F & pcct];
  182.  
  183.     pc2out [1] = pc2otab [4] [pcdt >> 21];
  184.     pc2out [1] |= pc2otab [5] [0X7F & (pcdt >> 14)];
  185.     pc2out [1] |= pc2otab [6] [0X7F & (pcdt >> 7)];
  186.     pc2out [1] |= pc2otab [7] [0X7F & pcdt];
  187.  
  188.     /* order key bits and bytes so as to be compatible with
  189.        the format generated by the E implementation */
  190.  
  191.     skedkeys [round] [0] = 0XFC00 & (pc2out [0] >> 8);
  192.     skedkeys [round] [0] |= (0XFC & (pc2out [0] >> 4));
  193.     skedkeys [round] [1] = 0XFC00 & (pc2out [1] >> 8);
  194.     skedkeys [round] [1] |= (0XFC & (pc2out [1] >> 4));
  195.  
  196.     skedkeys [round] [2] = 0XFC00 & (pc2out [0] >> 2);
  197.     skedkeys [round] [2] |= (0XFC & (pc2out [0] << 2));
  198.     skedkeys [round] [3] = 0XFC00 & (pc2out [1] >> 2);
  199.     skedkeys [round] [3] |= (0XFC & (pc2out [1] << 2));
  200.   }
  201. }
  202.  
  203. int parval ()  /* test parity of key in inkey; return 1 iff OK */
  204. {
  205.   int i, j;
  206.   int parac;
  207.   unsigned incopy;
  208.  
  209.   for (i = 0; i < 8; i++)       /* do each byte */
  210.   {
  211.     parac = 0;
  212.     incopy = inkey [i];
  213.  
  214.     for (j = 0; j < 8; j++)     /* 8 bits in a DES byte */
  215.     {
  216.       if (incopy & 01) parac++;
  217.       incopy >>= 1;
  218.     }
  219.     if (! (parac & 01)) return (0); /* no odd parity on this byte */
  220.   }
  221.   return (1);   /* OK on all of them */
  222. }
  223.  
  224. /* main for ksb -- accept and validate key, output schedule */
  225. main (argc, argv)
  226. int     argc;
  227. char    *argv [];
  228. {
  229.   extern unsigned skedkeys [16] [4];
  230.   extern unsigned inkey [8];
  231.  
  232.   int i, j;
  233.   FILE * fp, *fopen ();
  234.  
  235.   spc2otab ();  /* compute internal table */
  236.  
  237.   printf ("Enter DES key as 8 hex bytes: ");
  238.   scanf ("%x %x %x %x %x %x %x %x",
  239.     &inkey [0], &inkey [1], &inkey [2], &inkey [3],
  240.     &inkey [4], &inkey [5], &inkey [6], &inkey [7]);
  241.  
  242.   if (! parval ())
  243.   {
  244.     printf ("Bad parity on key... aborting...\n");
  245.     exit (1);
  246.   }
  247.  
  248.   ksmake ();
  249.  
  250.   
  251.   if (NULL == (fp = fopen (((argc > 1) ? argv [1] : "ks"), "w")))
  252.   {
  253.     printf ("ksb -- can't open output file '%s'\n",
  254.      ((argc > 1) ? argv [1] : "ks"));
  255.     exit (1);
  256.   }
  257.   
  258.   for (i = 0; i < 16; i++)      /* output entire schedule to file */
  259.   {
  260.     for (j = 0; j < 4; j++)
  261.       /* format is xxxxxx00xxxxxx00 */
  262.       fprintf (fp, "%x\n", skedkeys [i] [j]);
  263.   }
  264.   
  265.   printf ("ksb -- key schedule output to file '%s'\n",
  266.    ((argc > 1) ? argv [1] : "ks"));
  267. }
  268.  
  269.